package com.hanxiaozhang.tree;

/**
 * 〈一句话功能简述〉<br>
 * 〈请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。
 *   此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。
 *   如果从纸条的下边向上方连续对折2次，压出折痕后展开，
 *   此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
 *   给定一个输入参数N，代表纸条都从下边向上方连续对折N次。
 *   请从上到下打印所有折痕的方向。 〉
 *
 * @author hanxinghua
 * @create 2021/10/26
 * @since 1.0.0
 */
public class PaperFolding {


    public static void main(String[] args) {
        int N = 3;
        printAllFolds(N);
    }

    public static void printAllFolds(int N) {
        // 头结点一定是 凹节点
        printProcess(1, N, true);
    }

    /**
     * 递归过程，来到了某一个节点（二叉树的中序遍历）
     *
     * 特别是 第一次 凹节点 第二次 上凹 下凸 第三次 上凹 下凸
     *
     * @param i i是节点的层数
     * @param N N一共的层数，固定参数
     * @param down down == true  凹    down == false 凸
     */
    public static void printProcess(int i, int N, boolean down) {
        if (i > N) {
            return;
        }
        // 模拟左子树
        printProcess(i + 1, N, true);
        System.out.println(down ? "凹 " : "凸 ");
        // 模拟右子树
        printProcess(i + 1, N, false);
    }
}
